k-Nearest Neighbors (kNN)

L'algoritmo dei k-nearest neighbors (kNN) è uno degli algoritmi più semplici e intuitivi da implementare per la classificazione e la regressione. Questo algoritmo si basa sul principio che i dati simili tendono a essere vicini nello spazio delle caratteristiche. Utilizzando la vicinanza tra i punti dati, kNN determina la classe o il valore di un nuovo campione analizzando i k punti dati più vicini (detti vicini) nel dataset di addestramento.

La semplicità dell'algoritmo kNN risiede nella sua mancanza di una fase esplicita di addestramento: tutte le operazioni computazionali vengono eseguite solo quando si fa una previsione. Per questo motivo, kNN è spesso definito un algoritmo di apprendimento pigro (lazy learning), in contrapposizione agli algoritmi di apprendimento attivo (eager learning) che costruiscono modelli predittivi durante la fase di addestramento.

Descrizione dell'algoritmo

Il processo generale dell'algoritmo kNN può essere descritto con i seguenti passaggi:

1. Scegliere il numero di vicini k.
2. Calcolare la distanza tra il nuovo punto e tutti i punti nel dataset di addestramento.
3. Ordinare le distanze in ordine crescente e selezionare i k punti più vicini.
4. Per la classificazione, assegnare al nuovo punto la classe più frequente tra i k vicini. Per la regressione, assegnare al nuovo punto la media dei valori dei k vicini.

Definizione formale

Per formalizzare matematicamente l'algoritmo k-Nearest Neighbors (kNN), consideriamo un dataset di addestramento \( \mathcal{D} = \{(\mathbf{x}_i, y_i)\}_{i=1}^N \), dove \( \mathbf{x}_i \in \mathbb{R}^d \) rappresenta un vettore di lunghezza \( d \) (un punto dati con \( d \) caratteristiche) e \( y_i \in \mathbb{R} \) (o \( y_i \in \{1, \ldots, C\} \) dove \(C \in \mathbb{N}\), per la classificazione) rappresenta un'istanza della variabile target associata.

Assumiamo di aver osservato un insieme di \( n \) punti dati diversi. Queste osservazioni sono chiamate dati di addestramento perché li utilizziamo per addestrare il nostro modello su come stimare una funzione che ci permette di formalizzare la realtà di interesse. Lasciamo che \( x_{i,j} \) rappresenti il valore del \( j \)-esimo predittore, o input, per l'osservazione \( i \), dove \( i = 1, 2, \ldots, n \) e \( j = 1, 2, \ldots, d \). Di conseguenza, sia \( y_i \) la variabile di risposta per l'osservazione \( i \). I nostri dati di addestramento consistono in \( \{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \ldots, (\mathbf{x}_n, y_n)\} \), dove \( \mathbf{x}_i = (x_{i,1}, x_{i,2}, \ldots, x_{i,d})^T \).

Considerazioni sulla Scelta di k

La scelta del valore di k è cruciale per le prestazioni dell'algoritmo:

• Con k troppo piccolo, l'algoritmo può essere sensibile al rumore nei dati.
• Con k troppo grande, l'algoritmo può includere troppi punti che non sono realmente vicini.

Metriche di Distanza

Le metriche di distanza più comuni utilizzate nel kNN sono:

• Distanza Euclidea: \[ d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2} \]
• Distanza di Manhattan: \[ d(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^{n} |x_i - y_i| \]
• Distanza di Minkowski: \[ d(\mathbf{x}, \mathbf{y}) = \left( \sum_{i=1}^{n} |x_i - y_i|^p \right)^{1/p} \]

Vantaggi e Svantaggi

Vantaggi dell'algoritmo kNN:

• Semplice da implementare.
• Non richiede una fase di addestramento esplicita.
• Adatto a problemi sia di classificazione che di regressione.

Svantaggi dell'algoritmo kNN:

• Prestazioni dipendenti dalla scelta della metrica di distanza.
• Richiede spazio di memoria significativo per memorizzare tutti i dati di addestramento.
• Il tempo di predizione può essere elevato per dataset molto grandi.

Applicazioni

L'algoritmo kNN viene utilizzato in diverse applicazioni, tra cui:

• Riconoscimento di immagini.
• Sistemi di raccomandazione.
• Riconoscimento di modelli.
• Rilevamento di anomalie.